二分查找

704 二分查找

n 是 nums 列表中的元素数量。

时间复杂度：O(log n)，因为每次都将 nums 列表分割为一半，最多可以分割 log2(n) 次。

空间复杂度：

def search(nums: List[int], target: int) -> int:
  l, r = 0, len(nums) - 1
  mid = (l + r) // 2

  while l <= r:
    mid = (l + r) // 2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    else:
      break
  return mid if nums[mid] == target else -1

74 在 2D 矩阵中查找

875 柯克吃香蕉

def minEatingSpeed(piles: List[int], h: int) -> int:
  l, r = 1, max(piles)
  res = r

  while l <= r:
    k = (l + r) // 2
    total_time = 0

    for pile in piles:
      total_time += - ( - pile // k)
    
    if total_time <= h:
      res = k
      r = k - 1
    else:
      l = k + 1
  return res

153 查找旋转排序数组中的最小值

class Solution:
  def findMin(self, nums: List[int]) -> int:
    l, r = 0, len(nums) - 1

    while l < r:
      mid = (l + r) // 2
      if nums[mid] > nums[r]:
        l = mid + 1
      else:
        r = mid
    return nums[l]

981 基于时间的键值存储

class TimeMap:
  def __init__(self):
     self.table = {}  # {key: [timestamp, value]
    
  def set(self, key:str, value: str, timestamp: str) -> None:
    if key in self.table:
      self.table[key].append([timestamp, value])
    else:
      self.table[key] = [[timestamp, value]]
      
  def get(self, key:str, timestamp: str) -> str:
    if key in self.table:
      l, r = 0, len(self.table[key]) - 1

      while l <= r:
        mid = (l + r) // 2
        if self.table[key][mid][0] <= timestamp:
          l = mid + 1
        else:
          r = mid - 1
      
      return self.table[key][mid][1] 
    else:
      return ""